package _08_DFS_BFS;

import java.io.ByteArrayOutputStream;
import java.nio.file.Files;

public class _79_单词搜索 {

    public static void main(String[] args) {


        _79_单词搜索 v = new _79_单词搜索();

        char[][] chars = new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'},
        };
        boolean result = v.exist(chars, "ABCCED");

        System.out.println(result);
    }

    private char[] compareChar;

    private boolean isFind = false;

    private int rows;

    private int cols;

    private int[][] vertex = new int[][]{
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1},
    };

    public boolean exist(char[][] board, String word) {
        compareChar = word.toCharArray();
        rows = board.length;
        cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (isFind) return isFind;
                // 寻找初始值为
                if (board[i][j] == compareChar[0]) {
                    dfs(board, visited, i, j, 0);
                }
            }
        }
        return isFind;
    }

    private void dfs(char[][] board, boolean[][] visited, int row, int col, int index) {
        if (isFind || row < 0 || row >= rows || col < 0 || col >= cols || compareChar[index] != board[row][col] || visited[row][col]) return;
        // 从当前位置，上下左右寻找
        if (index == compareChar.length - 1) {
            // 寻找到当前值
            isFind = true;
            return;
        }
        visited[row][col] = true;
        for (int[] ints : vertex) {
            dfs(board, visited, row + ints[0], col + ints[1], index + 1);
            if (isFind) break;
        }
        visited[row][col] = false;
    }

}
